package main

import (
	. "whoops/leetcode/common"
)

//#link: https://leetcode-cn.com/problems/merge-k-sorted-lists/
func main() {

}

//合并k个有序链表
func mergeKLists(lists []*ListNode) *ListNode {
	lLen := len(lists)
	for lLen > 1 {
		idx := 0
		for i := 0; i < lLen; i = i + 2 {
			if i == lLen-1 {
				lists[idx] = lists[i]
			} else {
				lists[idx] = mergeTwoList(lists[i], lists[i+1])
			}
			idx++
		}
		lLen = idx
	}

	return lists[0]
}

func mergeTwoList(list1, list2 *ListNode) *ListNode {
	result := new(ListNode)
	temp := result
	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			temp.Next = list1
			list1 = list1.Next
		} else {
			temp.Next = list2
			list2 = list2.Next
		}
		temp = temp.Next
	}
	if list1 == nil {
		temp.Next = list2
	} else {
		temp.Next = list1
	}
	return result.Next
}
